МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ЗВІТ
З лабораторної роботи №2
з дисципліни “Алгоритми та методі обчислень”
на тему: “Асимптотичні характеристики складності алгоритму”
Варіант 8
1.Завдання:
1. Відповідно до варіанту завдання для заданих функцій часової складності L(n)
визначити асимптотичні характеристики O(n).
2. Розташувати отримані функції в порядку зростання асимптотичних характеристик
O(n).
3. Скласти програму (C), яка ілюструє клас (поліноміальний чи експоненціальний)
складності алгоритму, асимптотична складність якого була визначена в п2, як
найбільша. При складанні програми передбачити можливість зміни значень K та n.
2.Варіант завдання:
Номер варіанту – 8
/
3.Результат виконання програми:
Рис.1. Результат виконання програми
4.Висновок:
На даній лабораторній роботі я дізнався про асимптотичну складність алгоритму, визначив клас складності, та склав відповідну програму.
5.Код програми:
// don't forget to use compilation key for Linux: -lm
#define _CRT_SECURE_NO_WARNINGS // for using fopen in VS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#ifndef UINT
#define UINT unsigned long int
#endif
#ifndef USHORT
#define USHORT unsigned short
#endif
#ifndef UCHAR
#define UCHAR unsigned char
#endif
#define QDBMP_VERSION_MAJOR 1
#define QDBMP_VERSION_MINOR 0
#define QDBMP_VERSION_PATCH 1
typedef enum
{
BMP_OK = 0,
BMP_ERROR,
BMP_OUT_OF_MEMORY,
BMP_IO_ERROR,
BMP_FILE_NOT_FOUND,
BMP_FILE_NOT_SUPPORTED,
BMP_FILE_INVALID,
BMP_INVALID_ARGUMENT,
BMP_TYPE_MISMATCH,
BMP_ERROR_NUM
} BMP_STATUS;
typedef struct _BMP BMP;
BMP* BMP_Create(UINT width, UINT height, USHORT depth);
void BMP_Free(BMP* bmp);
BMP* BMP_ReadFile(const char* filename);
void BMP_WriteFile(BMP* bmp, const char* filename);
UINT BMP_GetWidth(BMP* bmp);
UINT BMP_GetHeight(BMP* bmp);
USHORT BMP_GetDepth(BMP* bmp);
void BMP_GetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR* r, UCHAR* g, UCHAR* b);
void BMP_SetPixelRGB(BMP* bmp, UINT x, UINT y, UCHAR r, UCHAR g, UCHAR b);
void BMP_GetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR* val);
void BMP_SetPixelIndex(BMP* bmp, UINT x, UINT y, UCHAR val);
void BMP_GetPaletteColor(BMP* bmp, UCHAR index, UCHAR* r, UCHAR* g, UCHAR* b);
void BMP_SetPaletteColor(BMP* bmp, UCHAR index, UCHAR r, UCHAR g, UCHAR b);
BMP_STATUS BMP_GetError();
const char* BMP_GetErrorDescription();
#define OUTPUT_SIZE 512
#define OUTPUT_WIDTH OUTPUT_SIZE
#define OUTPUT_HEIGHT OUTPUT_SIZE
#define NEIGHBOURHOOD 0
#define OUTPUT_SCALE 8
#define BMP_CHECK_ERROR( output_file, return_value ) \
if (BMP_GetError() != BMP_OK) \
{ \
fprintf((output_file), "BMP error: %s\n", BMP_GetErrorDescription()); \
return(return_value); \
}
void mark(BMP * bmpPtr, UINT neighbourhood, UINT xSize, UINT ySize, UCHAR pt) {
UINT neighbourhood2 = 2 * neighbourhood;
UINT xO, yO;
for (UINT x = 0; x < xSize; ++x) {
for (UINT y = 0; !y || (!(x % 20) && y < 10); ++y) {
for (xO = 0; xO <= neighbourhood2; ++xO) {
for (yO = 0; yO <= neighbourhood2; ++yO) {
if (x + xO >= neighbourhood && x + xO - neighbourhood < xSize && y + yO >= neighbourhood && y + yO - neighbourhood < ySize) {
BMP_SetPixelIndex(bmpPtr, x + xO - neighbourhood, ySize - (y + yO - neighbourhood), pt);
}
}
}
}
}
for (UINT y = 0; y < ySize; ++y) {
for (UINT x = 0; !x || (!(y % 20) && x < 10); ++x) {
for (xO = 0; xO <= neighbourhood2; ++xO) {
for (yO = 0; yO <= neighbourhood2; ++yO) {
if (x + xO >= neighbourhood && x + xO - neighbourhood < xSize && y + yO >= neighbourhood && y + yO - neighbourhood < ySize) {
BMP_SetPixelIndex(bmpPtr, x + xO - neighbourhood, ySize - (y + yO - neighbourhood), pt);
}
}
}
}
}
}
double functionForTabulate1(double arg) {
return sqrt(arg);
}
void tabulate(double(*functionPtr)(double arg), BMP * bmpPtr, UINT neighbour...
